A digital signature is proposed as a technology for securing the integrity of an electronic document. While developing utilization and application of the electronic document, a large number of demands exist for taking out a part of a signed electronic document, that is, extracting a part of the document. However, in a general digital signature, such an extraction is regarded as an alteration of the document, and the integrity may not be secured. As a technology for solving this, an applied digital signature technology is proposed for enabling a partial extraction by way of a sanitization signature and a deletion signature. These signatures may secure the integrity of the relevant part even when the extraction is performed.
Here, the extraction signature is defined. The general digital signature is defined by a two-person model including a signer for signing a signature and a verifier for performing verification. In contrast to this, in the extraction signature, as shown in FIG. 11, a three-person model is used including a signer for signing a signature, an extractor for extracting a part of the document signed by the signer, and a verifier for verifying the extracted document. The signer signs a document through any method. Then, the extractor receives the document and the signature. The extractor extracts a part of the received document, and generates extraction information and updates the signature accompanied by the extraction. Then, the verifier receives the extracted document and the signature as well as the extraction information. The verifier verifies that the extracted document is a part of the document signed by the signer on the basis of the extracted document and the signature as well as the extraction information. A signature scheme capable of satisfying the above-mentioned flow is defined as the extraction signature.
In order to perform the sanitization signature or the deletion signature, the document is divided into a plurality of partial documents in advance, and a signature processing or a part of the signature processing is performed with respect to those partial documents. According to the sanitization signature or the deletion signature in the related art, information on the signatures is enormous in proportion to the number of the partial documents at the time of signing. Also, the sanitization signature and the deletion signature in the related art need to have much extraction information in proportion to the number of the partial documents to be extracted at the time of extraction or the number of the partial documents to be deleted. For that reason, in order to extract a part of a large document, a great amount of signature information or a great amount of extraction information is prepared. That is, the signature system is extremely inefficient.
As a representative of the sanitization signature, for example, SUMI-4 is proposed. SUMI-4 is disclosed, for example, in Japanese Unexamined Patent Application Publication No. 2004-364070. According to this signature system, only one signature is used irrespective of the number of the partial documents. However, this signature system needs to have a hash value group of the partial documents to be deleted at the time of the extraction, and therefore the extraction information is increased in proportion to the number of the partial documents to be deleted.
This will be described with reference to FIGS. 12A and 12B. At the time of the signing, a signer divides document information M into partial document information m1 to m4, and partial document information ID information ID1 to ID4 are attached to the respective pieces of the partial document information to generate ID attached partial documents M1 to M4. Then, the signer calculates hash values h1 to h4 and signs with respect to the hash values h1 to h4 (a signature σ) to send the ID attached partial documents M1 to M4 and the signature σ to the extractor. At the time of the extraction, the extractor decides an ID attached partial document to be extracted. At this time, the extractor extracts the ID attached partial document M2. Then, the extractor calculates the hash values h1, h3, and h4 of the ID attached partial documents M1, M3, and M4 which are to be deleted, that is, which are not extracted and discloses h1, M2, h3, h4, and the signature σ of the signer to the public. That is, instead of the ID attached partial documents M1, M3, and M4 to be deleted, the hash values h1, h3, and h4 are disclosed. At the time of signature verification, by calculating the hash value h2 from the public ID attached partial document information M2, the verifier reconstructs the hash values h1 to h4 together with the public h1, h3, and h4 and performs the verification with the signature σ. As the signature σ is given with respect to the hash values h1 to h4 by the signer, the verifier may verify that the extracted ID attached partial document M2 is a part of the document M signed by the signer. At this time, in a case where the extraction is performed, if the hash value is not disclosed instead of the ID attached partial document to be deleted, the verifier may not perform the verification. For that reason, it is necessary to hold the “extraction information” which is the information in proportion to the number of the partial documents to be deleted, and if the number of the ID attached partial documents to be deleted is large, the extraction information necessary to be held becomes large.
Also, as a representative of the deletion signature, for example, SUMI-6 is proposed. SUMI-6 is disclosed, for example, in Japanese Unexamined Patent Application Publication No. 2006-60722. According to this signature system, it is necessary to hold indivisual signatures with respect to the respective partial documents and an entirety signature in which the indivisual signatures are aggregated at the time of the signing. For that reason, a problem occurs that the signature information is enlarged in proportion to the number of the partial documents.
This will be described with reference to FIGS. 13A and 13B. Similarly as in FIGS. 12A and 12B, at the time of the signing, the signer divides the document information M into the partial document information m1 to m4 and attaches the partial document information ID information ID1 to ID4 to the respective pieces of the partial document information to generate the ID attached partial documents M1 to M4. Then, the signer calculates the hash values h1 to h4 and also calculates indivisual Signatures σ1 to σ4 through an aggregate signature which will be described below and aggregates the indivisual signatures σ1 to σ4 to create an entirety signature σ. Finally, the signer sends the ID attached partial documents M1 to M4 and the indivisual signatures σ1 to σ4, and the entirety signature σ to the extractor. At the time of the extraction, the extractor decides the ID attached partial document to be extracted. At this time, it is set that the extractor extracts the ID attached partial document M2. The extractor deletes the ID attached partial documents M1, M3, and M4 which are not extracted and utilizes the corresponding indivisual signatures σ1, σ3, and σ4 to delete the information on σ1, σ3, and σ4 from the entirety signature σ for updating the entirety signature to σ′. Finally, the extractor discloses the extracted ID attached partial document M2 and the indivisual signature σ2, and the updated entirety signature σ′ to the public. At the time of the signature verification, the verifier verifies the public ID attached partial document information M2 and the updated entirety signature σ′. From the signature σ′, information on the indivisual signatures of the ID attached partial documents M1, M3, and M4 deleted by the extractor from the entirety signature σ of the signer is deleted. For that reason, the verifier may verify that the extracted ID attached partial document M2 is a part of the document M signed by the signer.
At this time, through this system, in a case where the signing is performed, the extraction may not be performed unless indivisual signature information is attached. For that reason, it is necessary to hold signature information in proportion to the number of the partial documents to be signed. That is, if the number of the ID attached partial documents to be signed is large, the signature information necessary to be held becomes large.
That is, in a sanitization signature based extraction, although the number of the signature used at the time of signing is one (small data amount), but in addition to the signature at the time of signing, extraction information by the number of the partial documents to be deleted needs to be held (large data amount) at the time of the extraction. In the deletion signature based extraction, at the time of extraction, the extracted document, an individual signature thereof, and the updated entirety signature are only used (small data amount), but in addition to the “entirety signature”, the “individual signatures” by the number of the partial documents needs to be held (large data amount) at the time of the signing.
On the other hand, an application technology on a digital signature called aggregate signature exists. With the aggregate signature, in a case where a signature needs to be assigned by one or a plurality of signers on one or a plurality of documents in an electronic document circulation, it is possible to reduce the signature data amount by aggregating the signatures.
A representative feature of the aggregate signature will be illustrated. In a case where a plurality of documents are signed by a plurality of signers, as shown in FIG. 14, when a standard digital signature is used, the signature data by the number of documents needs to be used. In contrast to this, when the aggregate signature is used, as shown in FIG. 15, it is possible to use one signature by aggregating the signatures of the respective documents. That is, it is possible to reduce the signature data amount.
Currently, as a construction method for the aggregate signature, for example, a sequential aggregate signature based on the RSA signature described in a document A. Lysyanskaya, et al., “Sequential Aggregate Signatures from Trapdoor Permutations,” EUROCRYPT 2004, LNCS 3027, pp. 74-90, 2004 is known. Also, a general aggregate signature based on pairing which is one of the elliptic curve cryptosystem technologies is known, which is described in a document described in D. Boneh, et al., “Aggregate and Verifiably Encrypted Signatures from Bilinear Maps”, EUROCRYPT 2003, LNCS 2656, pp. 416-432, 2003. The general aggregate signature is used in the above-mentioned deletion signature.
Furthermore, a technology called RSA accumulator is disclosed, for example, in a document, J. Benaloh, and M. de Mare, “One-way accumulators: A decentralized alternative to digital signatures,” EUROCRYPT '93, LNCS 765, pp. 274-285, Springer-Verlag, 1994. The RSA accumulator is one type of a hash function based on an RSA encryption and has an aggregation function. The RSA accumulator uses N which is a product of two prime numbers p, q like the RSA cryptosystem. Then, the RSA accumulator uses a generator g (which is coprime to N) with its order φ=LCM(p−1)(q−1). The RSA accumulator has a pseudo-commutative characteristic with assuming the RSA assumption. Herein, in all xεX and also all y1, y2εY, when a function f: X×Y→X satisfies the following characteristic, the function f has the pseudo-commutative characteristic.f(f(x,y1),y2)=f(x,y2),y1)
To elaborate, in a case where the function f is repeatedly applied any number of times, the function f has such a characteristic that the order may be changed, which is so-called commutative with respect to y. The RSA accumulator in the above-mentioned document realizes the function f by the following expression.fN(x,y)=xH(y)mod N 
Where, H denotes a unidirectional hash function which is, for example, SHA-1 or the like. In the RSA accumulator, the following relation is established.gH(y1)×H(y2)mod N=(gH(y1)mod N)H(y2)mod N=(gH(y2)mod N)H(y1) 
That is, aggregation of the hash values in no particular order may be realized. In addition to this, as the RSA accumulator has the unidirectional characteristic, from (gH(y)mod N) and H(y), N, it is assumed to be difficult to calculate y (so-called RSA assumption)
Incidentally, according to the above-mentioned sanitization signature technology, the deletion signature technology, and the sanitization and deletion technology, various states related to sanitization and deletion may be set to the respective partial documents. Here, the various states set to the respective partial documents will be described. It should be noted that a related technology is disclosed in “On sanitizable and deletable signature schemes”, M. Sano, T. Izu, N. Kunihiro, K. Ohta, and M. Takenaka, Proceedings of the Symposium on Cryptography and Information Security (SCIS2007), P. 156, January 2007.
FIG. 16 shows partial document states and state transients in the related art. In FIG. 16, a chart 3400 represents various states which may be set to the respective partial documents. To be specific, six states are represented in combination of prohibited, allowed, and sanitized/deleted related to the sanitization(hiding) and the deletion.
At this time, these six states are respectively denoted by SADA (sanitization allowed, deletion allowed), SPDP (sanitization prohibited, deletion prohibited), SADP (sanitization allowed, deletion prohibited), SDA (sanitized, deletion allowed), SDP (sanitized, deletion prohibited), and D (deleted).
Also, as state transients representing transients between these states, nine state transients Ta to Ti are represented. For example, the state transient Ta represents a transient from a state SADA in which the sanitization is allowed and also the deletion is allowed to a state SPDP in which the sanitization is prohibited and also the deletion is prohibited.
The above-mentioned six states and nine state transients are not simply set as properties with respect to the partial documents but are physically set through a data holding method. With this configuration, the partial documents may be set in various states in accordance with disclosure, nondisclosure, and capability or incapability of revision, and it is possible to prevent information leakage of the electronic document caused by a false setting of the properties.